package br.ufmg.dcc.paa;

import static br.ufmg.dcc.paa.collections.InstructionKind.BASE;
import static br.ufmg.dcc.paa.collections.InstructionKind.LOAD;
import static br.ufmg.dcc.paa.collections.InstructionKind.SIMPLE;
import static br.ufmg.dcc.paa.collections.InstructionKind.STORE;

import java.io.IOException;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

import br.ufmg.dcc.paa.collections.Graph;
import br.ufmg.dcc.paa.collections.Instruction;
import br.ufmg.dcc.paa.util.Parser;

public class AndersenAA {

	private Graph<String> pointsToGraph;
	private List<Instruction> instructions;
	
	public AndersenAA(String fileName) throws IOException {
		instructions = Parser.parse(fileName);
		pointsToGraph = new Graph<>();
		for (Instruction i : instructions) {
			pointsToGraph.add(i.getLeft());
			pointsToGraph.add(i.getRight());
		}
	}
	
	private void setUp() {
		for (Instruction i : instructions) {
			if (i.getConstraintName().equals(BASE)) {
				pointsToGraph.addValue(i.getLeft(), i.getRight());
			} else if (i.getConstraintName().equals(SIMPLE)) {
				pointsToGraph.addEdge(i.getRight(), i.getLeft());
			}
		}
	}
	
	public void generateAliasSet() {
		setUp();
		boolean changed;
		do {
			changed = false;
			//Set<String> origins = new HashSet<String>();
			for (Instruction i : instructions) {
				if (i.getConstraintName().equals(LOAD)) {
					for (String v : pointsToGraph.getValues(i.getRight())) {
						pointsToGraph.addEdge(v, i.getLeft());
						//origins.add(v);
						findAndColapseCycles(v);
					}
				} else if (i.getConstraintName().equals(STORE)) {
					for (String v : pointsToGraph.getValues(i.getLeft())) {
						pointsToGraph.addEdge(i.getRight(), v);
						//origins.add(i.getRight());
						findAndColapseCycles(i.getRight());
					}
				}
			}
			
			for (String u : pointsToGraph.getVertices()) {
				for (String v : pointsToGraph.getNeighbors(u)) {
					if (pointsToGraph.addAllValues(v, pointsToGraph.getValues(u)))
						changed = true;
				}
			}
		} while (changed);
	}
	
	private void findAndColapseCycles(String start) {
		pointsToGraph.initSearch();
		
		//DFS search
		Stack<String> s = new Stack<>();
		s.push(start);
		outer:while (!s.isEmpty()) {
			String u = s.pop();
			pointsToGraph.markAsVisited(u);
			for (String v : pointsToGraph.getNeighbors(u)) {
				if (pointsToGraph.isVisited(v)) {
					String node = u;
					
					//build the cycle
					List<String> cycle = new LinkedList<String>();
					cycle.add(start);
					while (pointsToGraph.getAncestor(node) != null && !node.equals(v)) {
						cycle.add(node);
						node = pointsToGraph.getAncestor(node);
					}
					
					pointsToGraph.collapse(cycle);
					
					break outer;
				} else {
					s.push(v);
					pointsToGraph.setAncestor(v, u);
				}
			}
		}
	}

	public boolean alias(String a, String b) {
		return pointsToGraph.getValues(a).contains(b);
	}
	
	public Map<String, Set<String>> aliasSets() {
		Map<String, Set<String>> aliasSets = new HashMap<String, Set<String>>();
		for (String v : pointsToGraph.getVertices()) {
			for (String label : v.split(","))
				aliasSets.put(label, pointsToGraph.getValues(v));
		}
		return aliasSets;
	}
	
}
